from bisect import *
from collections import deque

t = 3
class node():
    def __init__(self, k = None):
        self.n = 0
        self.keys = []
        self.isleaf = True
        self.cs = []
    def __str__(self):
        ret = '['
        for c in self.keys:
            ret += str(c)
        ret += ']'
        return ret
    def search(self, k):
        i = bisect_left(self.keys, k)
        if i <= self.n - 1 and k == self.keys[i]:
            return self, i
        elif self.isleaf:
            return None
        else:
            return self.cs[i].search(k)
    def split_child(self, i): 
        y = self.cs[i]
        z = node()
        z.isleaf = y.isleaf
        z.n = t - 1
        z.keys = y.keys[-(t - 1):]
        z.cs = y.cs[-t:]
        self.n += 1
        self.cs.insert(i + 1, z)
        self.keys.insert(i, y.keys[t - 1])
        y.n = t - 1
        y.keys = y.keys[:(t - 1)]
        y.cs = y.cs[:t]
    def insert_nonfull(self, k):
        if self.isleaf:
            insort_left(self.keys, k)
            self.n += 1
        else:
            i = bisect_left(self.keys, k)
            if self.cs[i].n == 2 * t - 1:
                self.split_child(i)
                if k > self.keys[i]: i += 1
            self.cs[i].insert_nonfull(k)
    def delete(self, k):
        if k in self.keys:
            if self.isleaf: #case 1
                self.keys.remove(k)
                self.n -= 1
            else: #case 2
                i = bisect_left(self.keys, k)
                if self.cs[i].n >= t: #case 2a
                    k = self.cs[i].keys[-1]
                    self.keys[i] = k
                    self.cs[i].delete(k)
                elif self.cs[i + 1].n >= t: #case 2b
                    k = self.cs[i + 1].keys[0]
                    self.keys[i] = k
                    self.cs[i + 1].delete(k)
                else: #case 2c
                    self.cs[i].keys.append(k)
                    self.cs[i].n += 1
                    self.cs[i].keys.extend(self.cs[i + 1].keys)
                    self.cs[i].n += self.cs[i + 1].n
                    self.cs[i].cs.extend(self.cs[i + 1].cs)
                    self.keys.pop(i)
                    self.n -= 1
                    self.cs.pop(i + 1)
                    self.cs[i].delete(k)
        else: #case 3
            i = bisect_left(self.keys, k)
            if self.cs[i].n == t - 1:
                if i - 1 >= 0 and self.cs[i - 1].n >= t: #case 3a.1
                    self.cs[i].keys.insert(0, self.keys[i])
                    self.cs[i].n += 1
                    self.cs[i].cs.insert(0, self.cs[i - 1].cs[-1])
                    self.keys[i] = self.cs[i - 1].keys[-1]
                    self.cs[i - 1].keys.pop()
                    self.cs[i - 1].n -= 1
                    self.cs[i - 1].cs.pop()
                elif i + 1 <= self.cs[i + 1].n and self.cs[i + 1].n >= t: #case 3a.2
                    self.cs[i].keys.append(self.keys[i])
                    self.cs[i].n += 1
                    self.cs[i].cs.append(self.cs[i + 1].cs[0])
                    self.keys[i] = self.cs[i + 1].keys[0]
                    self.cs[i + 1].keys.pop(0)
                    self.cs[i + 1].n -= 1
                    self.cs[i + 1].cs.pop(0)
                elif i - 1 >= 0 and self.cs[i - 1] == t - 1: #case 3b.1
                    self.cs[i - 1].keys.append(self.keys[i - 1])
                    self.cs[i - 1].n += 1
                    self.cs[i - 1].keys.extend(self.cs[i].keys)
                    self.cs[i - 1].n += self.cs[i].n
                    self.cs[i - 1].cs.extend(self.cs[i].cs)
                    self.keys.pop(i - 1)
                    self.n -= 1
                    self.cs.pop(i)
                    i -= 1
                else: #case 3b.2
                    self.cs[i].keys.append(self.keys[i])
                    self.cs[i].n += 1
                    self.cs[i].keys.extend(self.cs[i + 1].keys)
                    self.cs[i].n += self.cs[i + 1].n
                    self.cs[i].cs.extend(self.cs[i + 1].cs)
                    self.keys.pop(i)
                    self.n -= 1
                    self.cs.pop(i + 1)
            self.cs[i].delete(k)

class BTree():
    def __init__(self):
        self.root = node()
    def __str__(self):
        ret = ''
        q = deque()
        q.append(self.root)
        f = 1 # # in current level
        g = 0 # # in next level
        while len(q) > 0:
            cur = q.popleft()
            if not cur.isleaf:
                for c in cur.cs:
                    q.append(c)
                    g += 1
            ret += str(cur)
            f -= 1
            if f == 0:
                ret += '\n'
                f = g
                g = 0
        return ret
    def search(self, k):
        return self.root.search(k)
    def insert(self, k):
        r = self.root
        if r.n == 2 * t - 1:
            s = node()
            self.root = s
            s.isleaf = False
            s.n = 0
            s.cs = [r]
            s.split_child(0)
        self.root.insert_nonfull(k)
    def delete(self, k):
        self.root.delete(k)
        if self.root.n == 0:
            self.root = self.root.cs[0]

if __name__ == '__main__':
    b = BTree()
    b.root.keys = ['G','M','P','X']
    b.root.isleaf = False
    b.root.n = 4
    b.root.cs = [node() for i in xrange(5)]
    b.root.cs[0].keys = ['A','C','D','E']
    b.root.cs[0].n = 4
    b.root.cs[0].cs = [None] * 5
    b.root.cs[1].keys = ['J','K']
    b.root.cs[1].n = 2
    b.root.cs[1].cs = [None] * 3
    b.root.cs[2].keys = ['N','O']
    b.root.cs[2].n = 2
    b.root.cs[2].cs = [None] * 3
    b.root.cs[3].keys = ['R','S','T','U','V']
    b.root.cs[3].n = 5
    b.root.cs[3].cs = [None] * 6
    b.root.cs[4].keys = ['Y','Z']
    b.root.cs[4].n = 2
    b.root.cs[4].cs = [None] * 3
    
    print 'init tree:'
    print b
    INS = 'BQLF'
    for c in INS:
        b.insert(c)
        print 'after insert', c
        print b
        
    DEL = 'FMGDB'
    for c in DEL:
        b.delete(c)
        print 'after delete', c
        print b

